//
// Created by Administrator on 2023/8/8.
//
#include <iostream>

using namespace std;


//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *insertGreatestCommonDivisors(ListNode *head) {
        ListNode *a = head, *b = head->next;
        while (b != nullptr) {
            // 把节点 a 和 b 的 gcd 插到 ab 中间
            ListNode *node = new ListNode(gcd(a->val, b->val), b);
            a->next = node;
            // a 和 b 分别向后移动一个节点
            a = b;
            b = b->next;
        }
        return head;
    }

    int gcd(int a, int b) {
        // 计算最大公约数
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }


};

int main() {
    ListNode n1(18), n2(6), n3(10), n4(3);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    Solution s;
    auto head = s.insertGreatestCommonDivisors(&n1);
    // 打印整个链表
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}